"""
Fibonacci （斐波那契 数列）
1, 1, 2, 3, 5, 8, 13, 21 ......
fib(n) = 1  n = 1 or 2
       = fib(n-1) + fib(n-2)
"""
import time

memo = {}


def fiboRecursion(n):
    # 递归解法 recursion
    if n == 1 or n == 2:
        return 1
    else:
        return fiboRecursion(n-1) + fiboRecursion(n-2)


def fiboRecursionMemo(n):
    if n == 1 or n == 2:
        return 1
    elif n in memo:
        # 利用hash表缓存返回已知数据
        return memo[n]
    else:
        res = fiboRecursionMemo(n-1)+fiboRecursionMemo(n-2)
        memo[n] = res
        return res


def fiboGeneration(n):
    a, b = 0, 1
    while n:
        a, b = b, a+b
        yield a
        n -= 1


if __name__ == '__main__':
    begin_t = time.time()
    # print(fiboRecursion(35))
    print(fiboRecursionMemo(5))
    print(fiboRecursionMemo(100))
    print(memo)
    end_t = time.time()
    print(end_t-begin_t)
    for i in fiboGeneration(5):
        print(i)




